package search.binarysearch;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/26 10:34
 * @Description
 */
public class Upper {

    public static void main(String[] args) {
        Integer[] arr = {1,1,3,3,5,5};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(Upper.lowerCeil(arr,i));
        }


    }

    //upper
    public static <E extends Comparable<E>> int upper(E[] data,E target){
        //如果整个数组中都没有比target小的值，就返回data[data.length]
        int l = 0,r=data.length;
        while(l<r){
            int mid = l+(r-l)/2;
            if(data[mid].compareTo(target)>0){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return r;
    }

    //ceil
    public static <E extends Comparable<E>> int ceil(E[] data,E target){
        int upper = upper(data, target);
        if(upper-1>=0&&data[upper-1].compareTo(target)==0){
            return upper-1;
        }
        return upper;
    }

    //lowerCeil
    public static <E extends Comparable<E>> int lowerCeil(E[] data,E target){
        int upper = upper(data, target);
        if(upper-1>=0&&data[upper-1].compareTo(target)==0){
           for(int i = upper-1;i>=0;i--){
               if(data[i].compareTo(target)<0){
                   return i+1;
               }
           }
           return 0;
        }
        return upper;
    }

    //lower
    public static <E extends Comparable<E>> int lower(E[] data,E target){
        int l = -1,r=data.length-1;
        while(l<r){
            int mid = l+(r-l+1)/2;
            if(data[mid].compareTo(target)<0){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        return r;
    }

}
